package com.hy.study.algorithm.dac;

/**
 * 分治算法求解汉诺塔
 */
public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(32, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔
     *
     * @param num 一共有多少个汉诺塔
     * @param a   A柱
     * @param b   B柱
     * @param c   C柱
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        //如果只有一个盘 从A直接移动到C
        if (num == 1) {
            System.out.println("第1个盘从 " + a + "-->" + c);
        } else {
            //有多个盘
            //我们总是看成2个盘，上面的所有盘+ 最底层的一个
            //1.先把上面的所有盘 A-B ,移动过程会使用到C
            hanoiTower(num - 1, a, c, b);
            //2.把最下边的盘 A-->C
            System.out.println("第 " + num + "个盘从" + a + "-->" + c);
            //3.把B塔的所有盘从B-->C,移动过程中使用到A
            hanoiTower(num - 1, b, a, c);
        }
    }
}
